This invention relates to the field of arithmetic and logic techniques in computer and processor architecture, in particular, the design of a binary multiplier use for use with functionalities found in a common processor environment.
Binary multiplication is the subset of the multiplication operations that deal only with whole numbers, both signed and unsigned, and whose operands and results are therefore fully representable in binary. The simplest method for binary multiplication imitates the human method of execution by which the multiplicand is processed by the multiplier one multiplier digit at a time to form a partial product, and the partial products are summed to form the final product. An example of the human multiplication method as applied to binary numbers is as follows.Unsigned Multiplication (4-bit×4-bit->8-bit for full result representation)
                                                                                                1              1              1              0              multiplicand              14                                                                                                      0              1              1              1              multiplier              07                                                                                                      …              …              …              …                                                                            ⁢        …                                                                                1              1              1              0                                                  pp        ⁢                                  ⁢        1                    98                                              1              1              1              0                                                                              pp        ⁢                                  ⁢        2                    00                  1              1              1              0                                                                                                          pp        ⁢                                  ⁢        2                    ⋯                  0              0              0              0                                                                                                          pp        ⁢                                  ⁢        3                                                    ⋯              ⋯              ⋯              ⋯              ⋯              ⋯              ⋯                                                                          0              1              1              0              0              0              1                      0        ⁢                                  ⁢        product                    98      
The method also works for signed multiplication. However, using 2's complement negative representation and sign extension makes additional processing of the result sign unnecessary.Signed Multiplication (4-bit×4-bit->8-bit with operands sign-extended to 8)
            1              1              1              1              1              1              1              0              multiplicand                      -        2                        0              0              0              0              0              1              1              1              multiplier                      +        7                                                                                                                                                                                                                                                        ⋯              ⋯                  1              1              1              1              1              1              1              0                      pp        ⁢                                  ⁢        1                            -        14                        1              1              1              1              1              1              0                                                  pp        ⁢                                  ⁢        2                                                    1              1              1              1              1              0                                                                              pp        ⁢                                  ⁢        3                                                    0              0              0              0              0                                                                                                          pp        ⁢                                  ⁢        4                                                    0              0              0              0                                                                                                                                      pp        ⁢                                  ⁢        5                                                    0              0              0                                                                                                                                                                  pp        ⁢                                  ⁢        6                                                            0        ⁢                                              0                                                                                                                                                                                              pp        ⁢                                  ⁢        7                                                    0                                                                                                                                                                                                                          pp        ⁢                                  ⁢        8                                                    ⋯              ⋯              ⋯              ⋯              ⋯              ⋯              ⋯              ⋯                                                                          1              1              1              1              0              0              1              0              product                      -        14            
While this method of multiplication is very simple and relatively easy to implement in hardware with a shifter, an adder, and a product accumulator, if it takes one cycle to process one multiplier bit to form a partial product, an operation with an n-bit multiplier will take in the order of n cycles to finish. Such a long cycle-per-instruction (CPI) time in the current world of high-speed computing is considered a prohibitive solution to achieving to shorter CPI for multiply instructions is to expend additional hardware to calculate the partial products in groups at a time and build the necessary adders to process them simultaneously. This brute force approach of throwing hardware at the problem does decrease CPI but it also increases the chip area dedicated to the multiplication functions. Adders in particular, are difficult to handle, especially with the area and timing constraints that usually accompany the functional specifications. Many methods have therefore been formulated to decrease adder size through decreasing of partial products by processing the multiplier multiple bits at a time. One of the more popular methods is the Booth recoding algorithm.
The Booth recoding algorithm is a method for reducing the number of partial products produced from a given n-bit multiplier through multiple-bit scanning. It is based on the concept that a string of binary ones, where the least significant bit of value ‘1’ holds a significant value of 2n and the string of ones is z bits long, may alternatively be represented as 2n+z−2n. For example, the string 0b0111 may be represented as 23−20=7, and the string 0b1110 as 24−21=14.
In the previous example, the weight of each bit is equal to 2n where n is the positional value of the relevant bit. The detection of a string of ones is done by overlapping the scanned group of multiplier bits by one bit. Applying this counting method to multiplication, where the scanned number is the multiplier in a 1-bit scan with an overlapping bit, is as simple as giving a bit that is at the end of a string (the least significant bit in the string), detected by a ‘1’ bit whose overlapping bit to the right is a ‘0’, a value of −(2n)*(multiplicand); a bit that is at the beginning of the string (the most significant bit of the z-bit string), detected by a ‘0’ in the position with the overlap bit equal to ‘1’, a value of (2n)*(multiplicand); and a bit that is in the middle of a string of 0's or 1's a value of zero. This is summarized in the table below, where the leftmost bit is the bit in position n of the string and the rightmost bit is the overlap bit needed for string detection. The “Justified Multiplicand Value” column gives the multiplicand-multiple value, the significance of this value may be implied with the position of the relevant scanned bit.
TABLE 1Truth-Table For Radix-2 Booth RecodingMULTIPLICANDJUSTIFIED MULTIPLICAND2-BIT SCANVALUEVALUE000x  0x01(+2n)x+1x10(−2n)x−1x110x  0x
The key to advantageous implementation of the Booth recoding method is in increasing the number of bits that are scanned in a group, thereby decreasing the overall necessary scans of the multiplier as well as the number of partial products and the hardware necessary to combine the partial products. A popular scan-group size is 3 bits, composed of 2 scanned bits with an overlap bit in the least significant position. Its popularity is based on the fact that the necessary multiplicand-multiples needed to realize the recoding is simply 0×, ±1×, and ±2×, all relatively easy to formulate using shifters, inverters, and two's complementation methods to realize all possible multiples, whereas larger scan-group sizes necessitate adders to formulate higher multiples such as ±3×.